package com.test.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 希尔排序
 * 
 * @author xuguangqiao
 *
 */
public class ShellSort {

	/**
	 * 希尔排序
	 * @param arr
	 * @return
	 */
	public static int[] sellSort(int[] arr) {

		// 计算出最大的h值
		int h = 1;
		while (h <= arr.length / 3) {
			h = h * 3 + 1;
		}
		while (h > 0) {
			for (int i = h; i < arr.length; i++) {
				if (arr[i] < arr[i - h]) {
					int tmp = arr[i];
					int j = i - h;
					while (j >= 0 && arr[j] > tmp) {
						arr[j + h] = arr[j];
						j -= h;
					}
					arr[j + h] = tmp;
				}
			}
			// 计算下一个h值
			h = (h - 1) / 3;
		}

		return arr;
	}

	/**
	 * 奇偶交换排序
	 * @param arr
	 * @return
	 */
	public static int[] oddEventSort(int[] arr) {
		int exchFlag = 1, start = 0;
		while (exchFlag == 1 || start == 1) {
			exchFlag = 0;
			for (int i = start; i < arr.length - 1; i += 2) {
				if (arr[i] > arr[i + 1]) {
					int temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
					exchFlag = 1;
				}
			}
			if (start == 0) {
				start = 1;
			} else {
				start = 0;
			}
		}
		return arr;
	}

	/**
	 * 插入排序
	 * @param arr
	 * @return
	 */
	public static int[] innsertSort(int[] arr) {

		int len = arr.length;
		int j, i, key;

		for (i = 1; i < len; i++) {
			// key为要准备插入的元素
			key = arr[i];
			j = i - 1;
			while (j >= 0 && arr[j] > key) {
				arr[j + 1] = arr[j];
				j--;
			}
			// 找到合适的位置插入key
			arr[j + 1] = key;
			//System.out.println(Arrays.toString(arr));
		}
		return arr;
	}
	public static void main(String[] args) {
		int len = 10000;
		int[] arr = new int[len];
		int[] arr2 = new int[len];
		int[] arr3 = new int[len];
		Random random = new Random();
		for (int i = 0; i < arr.length; i++) {
			arr[i] = random.nextInt(100000);
		}
		System.arraycopy(arr, 0, arr2, 0, len);
		System.arraycopy(arr, 0, arr3, 0, len);
		//System.out.println(Arrays.toString(arr));
		System.out.println("---------shellSort------------");
		long start = System.currentTimeMillis();
		sellSort(arr);
		long end = System.currentTimeMillis();
		//System.out.println(Arrays.toString(arr));
		System.out.println(end - start);
		System.out.println("---------oddEventSort------------");
		start = System.currentTimeMillis();
		OddEventSort.oddEventSort(arr2);
		end = System.currentTimeMillis();
		System.out.println(end - start);
		//System.out.println(Arrays.toString(arr2));
		System.out.println("---------insetSort------------");
		start = System.currentTimeMillis();
		InsertSort.innsertSort(arr3);
		end = System.currentTimeMillis();
		System.out.println(end - start);

	}
}
